import java.util.*;

/*
 * @lc app=leetcode.cn id=15 lang=java
 *
 * [15] 三数之和
 */

// @lc code=start
class Solution {
    List<List<Integer>> ret = new ArrayList<List<Integer>>();

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length == 0)
            return ret;

        // 先对数组进行排序  O(nlogn)
        Arrays.sort(nums);
        // for(int i : nums) System.out.println(i);

        for (int left = 0; left < nums.length; left++) {
            // 跳过左侧重复的数字
            if (left > 0 && nums[left] == nums[left - 1])
                continue;

            // p3是右侧的指针
            int right = nums.length - 1;

            // 思路是，先从左往右遍历mid，此时right一定不会右移，所以right被动左移
            // 所以事实上2个指针的移动只有O(n)复杂度
            for (int mid = left + 1; mid < right; mid++) {
                // 让mid指针跳过重复的数值
                if (mid > left + 1 && nums[mid] == nums[mid - 1])
                    continue;

                // 这里的符号非常重要，因为mid和left定了之后，right一开始是取最大的
                // 所以判断是不是和大于0，如果一开始就小于0，那么这个left和mid就不可能对应一个right
                // 如果一开始确实大于0，也才有可能找到合适的right
                while (nums[left] + nums[right] + nums[mid] > 0 && right > mid) {
                    right--;
                }
                if (right == mid)
                    break;
                if (nums[left] + nums[right] + nums[mid] == 0) {

                    ret.add(new ArrayList<Integer>(
                            Arrays.asList(new Integer[] { nums[left], nums[mid], nums[right] })));
                }

            }

        }

        return ret;

    }
}

// @lc code=end
